﻿using System;
using System.Linq;

namespace BackTracking
{
    /* problem description 
     * 
     * The knight is placed on the empty board and, 
     * moving according to the rules of chess, must visit each square exactly once. 
     * 
     * Here is the link to the original page: http://www.geeksforgeeks.org/archives/12916
     */

    class KnightTour
    {
        /* algorithm:
         * If all squares are visited
                print the solution
           Else
                a) Add one of the next moves to solution vector and recursively
                   check if this move leads to a solution. (A Knight can make maximum
                   eight moves. We choose one of the 8 moves in this step).
                b) If the move chosen in the above step doesn't lead to a solution
                   then remove this move from the solution vector and try other alternative moves.
                c) If none of the alternatives work then return false (Returning false
                   will remove the previously added item in recursion and if false is
                   returned by the initial call of recursion then "no solution exists" )
        */

        static int N = 8; 
        
        /* A utility function to check if i,j are valid indexes for N*N chessboard */
        bool isSafe(int i, int j, int[,] sol)
        { 
            if ( i >= 0 && i < N && j >= 0 && j < N && sol[i,j] == 0)    
                return true;   
            
            return false;
        } 
        
        /* A utility function to print solution matrix sol[N][N] */
        void printSolution(int[,] sol)
        {   
            for (int i = 0; i < N; i++)   
            {     
                for (int j = 0; j < N; j++)      
                    Console.Write(" {0} ", sol[i,j]);

                Console.WriteLine();
            }
        } 
        
        /* This function solves the Knight Tour problem using Backtracking.  
         * Thisfunction mainly uses solveKTUtil() to solve the problem. 
         * It returns false ifno complete tour is possible, 
         * otherwise return true and prints the tour.
         * Please note that there may be more than one solutions, 
         * this function prints one of the feasible solutions.  
         */
        bool solveKT()
        {
            int[,] sol = new int[N,N] ;   

            /* Initialization of solution matrix */   
            for (int i = 0; i < N; i++)     
                for (int j = 0; j < N; j++)  
                    sol[i,j] = 0;    
            
            /* a[] and b[] define next move of Knight.      
             * a[] is for next value of x coordinate      
             * b[] is for next value of y coordinate 
             */   
            int[] a = {  2, 1, -1, -2, -2, -1,   1,  2};   
            int[] b = {  1, 2,  2,  1,  -1, -2,  -2, -1 };
            
            /* Start from 0,0 and explore all tours using solveKTUtil() */   
            if(solveKTUtil(0, 0, 1, sol, a, b) == false)   
            {
                Console.WriteLine("Solution does not exist");     
                return false;
            } 
            else   
            { 
                printSolution(sol);   
            } 
            
            return true;
        }
        
        /* A recursive utility function to solve Knight Tour problem */
        bool solveKTUtil(int x, int y, int movei, int[,] sol, int[] a, int[] b)
        {
            int k, u, v;    
            if (movei == N*N)     
                return true;    
            else    
            { 
                /* Try all next moves from the current coordinate x, y */      
                for (k = 0; k < N; k++)
                {
                    u = x + a[k];
                    v = y + b[k];   
                    
                    if (isSafe(u, v, sol) == true)
                    {
                        sol[u,v] = movei; 
                        
                        if( solveKTUtil(u, v, movei+1, sol, a, b) == true)
                            return true;    
                        else 
                            sol[u,v] = 0;// backtracking
                    }
                }
            }

            return false;
        } 
        
        /* Driver program to test above functions */
        static void Main(string[] args)
        {
            KnightTour knight = new KnightTour();
            knight.solveKT();

            Console.WriteLine("Press any key to finish...");
            Console.ReadKey();
        }
    }
}
